package com.cy.tree;

import java.util.Stack;

/**
 * @Author: cy
 * @Date: 2021/09/26/15:41
 * @Description:
 * 非递归方法：先序、中序、后序遍历树
 */
// 借用栈实现非递归方法打印链表
public class Demo2 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        System.out.println("先序遍历顺序是：");
        recursivePreOrder(node1); //先序遍历
        System.out.println();
        System.out.println("中序遍历顺序是：");
        recursiveInOrder(node1);
        System.out.println();
        System.out.println("后序遍历顺序是：");
        recursivePostOrder(node1);
    }



    /**
     *          1
     *        2   3
     *      4  5 6 7
     * 非递归 先序遍历  根左右
     * 思路：
     * 1、根节点入栈
     * 2、从栈中弹出一个节点cur
     * 3、打印(处理)cur
     * 4、先右节点再左节点入栈(如果有)
     * 5、重复步骤2-4
     * @param head
     */
    public static void recursivePreOrder(Node head){
        Stack<Node> stack = new Stack<>();
        stack.push(head);  //根节点入栈
        while (!stack.isEmpty()){
            Node cur = stack.pop(); //弹出一个节点
            System.out.print(cur.value+" ");  //打印弹出节点
            if(cur.right != null){  //弹出节点如果存在右节点,右节点入栈
                stack.push(cur.right);
            }
            if(cur.left != null){   //弹出节点如果存在左节点,左节点入栈
                stack.push(cur.left);
            }
        }
    }


    /**
     *          1
     *        2   3
     *      4  5 6 7
     * 非递归 中序遍历  左根右
     * 思路：
     * 1、每颗子树，整课树左边界进栈
     * 2、依次弹出的过程中打印
     * 3、如果弹出节点存在右树，右树入栈
     * 4、重复3
     *
     * 例如：
     * 1 2 4进栈    4弹出，因为4没有右节点所以继续弹出2    对2右树周而复始
     * 5进栈   5弹出，因为5没有右节点所以继续弹出1    对1右树周而复始   3,6进栈
     * 弹出6无右树  继续弹出3   对3右树周而复始  7进栈  弹出7
     * 4,2,5,1,6,3,7
     * @param head
     */
    public static void recursiveInOrder(Node head){

        if(head != null){
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                }else {
                    head = stack.pop();
                    System.out.print(head.value+" ");
                    head = head.right;
                }
            }
        }

    }


    /**
     *            1
     *          2   3
     *        4  5 6 7
     *  非递归 后序遍历  左右根
     *  思路：借助两个栈   先左子树再右子树入栈  栈的输出为 根右左  然后放入收集栈，收集栈输出左右根
     *  1、根节点入栈
     *  2、从栈中弹出一个节点cur
     *  3、将cur放入收集栈
     *  4、先左子树再右子树入栈(如果有)
     *  5、重复步骤2-4
     * @param head
     */
    public static void recursivePostOrder(Node head){
        Stack<Node> stack = new Stack<>();
        Stack<Node> collectionStack = new Stack<>();   //收集栈
        stack.push(head);   //头节点入栈
        while (!stack.isEmpty()){
            Node cur = stack.pop(); //弹出一个节点
            collectionStack.push(cur);  //将弹出节点放入收集栈中
            if(cur.left != null){
                stack.push(cur.left);   //弹出节点如果存在左节点,左节点入栈
            }
            if(cur.right != null){
                stack.push(cur.right);  //弹出节点如果存在右节点,右节点入栈
            }
        }
        //在将收集栈中的所有数据弹出
        while (!collectionStack.isEmpty()){
            System.out.print(collectionStack.pop().value+" ");
        }

    }
}
